package ljl.codetop;

import java.util.ArrayList;
import java.util.List;

public class _22_gen_par {

    /**
     * 我记着是回溯
     * 我丢过啦，背的不赖
     */
    static class tryout {
        // 这用 byte[] 或 stringBuilder，对性能居然没任何影响。看来性能永远不是最主要的...
        byte[] buf;
        List<String> res = new ArrayList<>();
        public List<String> generateParenthesis(int n) {
            buf = new byte[n * 2];
            backtrack(0, 0, 0, n);
            return res;
        }

        /**
         * 某一个位置只能是左或右括号
         * 一般都能是左，选了左可以看看是不是也能选右
         */
        void backtrack(int pos, int left, int right, int n) {
            if (left == n && right == n) {
                res.add(new String(buf));
                return;
            }
            if (left < n) {
                buf[pos] = '(';
                backtrack(pos + 1, left + 1, right, n);
            }
            if (left > right) {
                buf[pos] = ')';
                backtrack(pos + 1, left, right + 1, n);
            }
        }
    }

    /**
     * 这个不好想，效率也不太高
     * 归纳出来所有括号都有 (a)b 这种格式，a 和 b 可以是任何合法括号组合包括空字符串
     */
    static class off3 {
        @SuppressWarnings("unchecked")
        List<String>[] cache = new List[9];
        public List<String> generateParenthesis(int n) {
            if (cache[n] != null)
                return cache[n];
            List<String> res = new ArrayList<>();
            cache[n] = res;
            if (n == 0) {
                res.add("");
            } else {
                for (int i = 0; i < n; i++) {
                    for (String left : generateParenthesis(i)) {
                        for (String right : generateParenthesis(n - i - 1)) {
                            res.add("(" + left + ")" + right);
                        }
                    }
                }
            }
            return res;
        }
    }
}
